//2009/07/27 10:28:51
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

class MNS
{
public:
	int combos(vector <int> numbers)
	{
		int score = 0;
		set<vector<int> > v;
		sort(numbers.begin(), numbers.end());

		if(checkMagic(numbers))
		{
			score++;
			v.insert(numbers);
		}

		while(next_permutation(numbers.begin(), numbers.end()))
		{
			if(checkMagic(numbers))
			{
				int sz = v.size();
				v.insert(numbers);
				if(sz != v.size())
					score++;
			}
		}
		return score;
	}
private:
	bool checkMagic(vector<int> nn)
	{
		set<int> s;
		s.insert(nn[0] + nn[1] + nn[2]);
		s.insert(nn[3] + nn[4] + nn[5]);
		s.insert(nn[6] + nn[7] + nn[8]);

		s.insert(nn[0] + nn[3] + nn[6]);
		s.insert(nn[1] + nn[4] + nn[7]);
		s.insert(nn[2] + nn[5] + nn[8]);

		return (s.size() == 1);
	}
};

/*  From Topcoder editorials.
	C++ coders can use the built in next_permutation function for a similar effect.
	//Members of vals must be distinct
//Based on C++ next_permutation function
int[] nextperm(int[] vals) {
   int i =  vals.length-1;
   while (true) {
      int ii =  i;
      i--;
      if (vals[i] < vals[ii]) {
         int j = vals.length;
         while (vals[i] >= vals[--j]);
            int temp = vals[i];  //Swap
            vals[i] = vals[j]; 
            vals[j] = temp;
         int begin = ii, end = vals.length-1;
         while (end>begin) {
               int stemp = vals[end];   //Swap
               vals[end] = vals[begin]; 
               vals[begin] = stemp;
            end--; begin++;
         }   
         return vals;
      } else if (vals[i] == vals[0]) {
         int begin = 0, end = vals.length-1;
         while (end>begin) {
               int stemp = vals[end];   //Swap
               vals[end] = vals[begin]; 
               vals[begin] = stemp;
            end--; begin++;
         }   
         return vals;
      }
   }
}

Since nextperm only works on lists of numbers without duplicates we will use a sort of hack to get it to work. 
Generate an array containing the numbers 0-8. Permute that array to get all permutations. 
Use the permuted list of numbers at any one point as the ordering to impose on the actual list that may contain duplicates. 

In this case, the author used a set to check whether exists duplicates.
*/
